package org.autumn.structure.tree;

/**
 * 二叉树
 * 每个节点最多有两个子节点
 * <p>
 * 节点的遍历
 * 先序：是二叉树遍历中的一种，即先访问根结点，然后遍历左子树，后遍历右子树。遍历左、右子树时，先访问根结点，后遍历左子树，后遍历右子树，如果二叉树为空则返回。
 * <p>
 * 中序：是二叉树遍历中的一种，即先遍历左子树，后访问根结点，然后遍历右子树。若二叉树为空则结束返回。
 * <p>
 * 后序：是二叉树遍历中的一种，即先遍历左子树，后遍历右子树，然后访问根结点，遍历左、右子树时，仍先遍历左子树，后遍历右子树，最后遍历根结点。
 */
public class LinkedBinaryTree {

    private Node root;

    public void add(int id) {
        Node addition = new Node(id, null, null);
        if (root == null) {
            root = addition;
        } else {
            Node node = root;
            while (true) {
                // 如果id小于当前树id,存入左子树,否则右子树
                if (id < node.id) {
                    Node left = node.getLeft();
                    if (left == null) {
                        node.left = addition;
                        return;
                    }
                    node = left;
                } else {
                    Node right = node.getRight();
                    if (right == null) {
                        node.right = addition;
                        return;
                    }
                    node = right;
                }
            }

        }
    }

    public void preOrder(Node node) {
        System.out.print(node.getId() + "\t");
        if (node.left != null) {
            preOrder(node.left);
        }
        if (node.right != null) {
            preOrder(node.right);
        }
    }

    public void infixOrder(Node node) {
        if (node.left != null) {
            infixOrder(node.left);
        }
        System.out.print(node.getId() + "\t");

        if (node.right != null) {
            infixOrder(node.right);
        }
    }

    public void postOrder(Node node) {
        if (node.left != null) {
            postOrder(node.left);
        }
        if (node.right != null) {
            postOrder(node.right);
        }
        System.out.print(node.getId() + "\t");
    }


    public int treeDepth(Node node) {
        if (node == null) {
            return 0;
        }
        int nLeft = treeDepth(node.left);

        int nRight = treeDepth(node.right);

        return (nLeft > nRight) ? nLeft + 1 : nRight + 1;

    }

    public Node getRoot() {
        return root;
    }

    // 节点
    class Node {
        private int id;
        private Node left;
        private Node right;

        public Node() {
        }

        public Node(int id, Node left, Node right) {
            this.id = id;
            this.left = left;
            this.right = right;
        }

        public int getId() {
            return id;
        }

        public void setId(int id) {
            this.id = id;
        }

        public Node getLeft() {
            return left;
        }

        public void setLeft(Node left) {
            this.left = left;
        }

        public Node getRight() {
            return right;
        }

        public void setRight(Node right) {
            this.right = right;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "id=" + id +
                    '}';
        }
    }
}
